public class merge {


    public static void merge(int[] elem){
        int gap = 1;
        while (gap < elem.length){
            for(int i = 0; i <= elem.length;i = 2*gap + i){
                int left = i;
                int mid = left + gap - 1;
                if (mid >= elem.length){
                    mid = elem.length-1;
                }
                int right = mid + gap;
                while (right >= elem.length){
                    right = elem.length - 1;
                }
                merge(elem,left,mid,right);
            }
            gap *=2;
        }
    }

    public static void merge(int[] elem,int left,int mid,int right){
        int[] tem = new int[right - left + 1];
        int i = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        while (s1 <= e1 && s2 <= e2){
            if (elem[s1] <= elem[s2]){
                tem[i++] = elem[s1++];
            }else {
                tem[i++] = elem[s2++];
            }
        }
        while (s1 <= e1){
            tem[i++] = elem[s1++];
        }
        while (s2 <= e2){
            tem[i++] = elem[s2++];
        }
        for (int j = 0; j < tem.length; j++) {
            elem[left + j] = tem[j];
        }
    }

}
